package com.itheima.leetcode;

/**
 * 反转链表
 *
 * @FileName E01LeetCode206
 * @Description
 * @Author Sword
 * @date 2025-03-18
 **/
public class E01LeetCode206 {

    //方法1
    public static ListNode reverseList1(ListNode o1) {
        ListNode n1 = null;
        ListNode p = o1;
        while (p != null) {
            n1 = new ListNode(p.val, n1);
            p = p.next;
        }

        return n1;
    }

    //方法2
    public static ListNode reverseList2(ListNode head) {
        List list1 = new List(head);
        List list2 = new List(null);
        while (true) {
            ListNode first = list1.removeFirst();
            if (first == null) {
                break;
            }
            list2.addFirst(first);
        }

        return list2.head;
    }

    static class List {
        ListNode head;

        public List(ListNode head) {
            this.head = head;
        }

        public void addFirst(ListNode first) {
            first.next = head;
            head = first;
        }

        public ListNode removeFirst() {
            ListNode first = head;
            if (first != null) {
                head = first.next;
            }

            return first;
        }
    }

    //方法3   递归
    public static ListNode reverseList3(ListNode p) {
        if (p == null || p.next == null) {
            return p;   //最后节点
        }
        ListNode last = reverseList3(p.next);
        p.next.next = p;
        p.next = null;
        return last;
    }

    //方法4
    public static ListNode reverseList4(ListNode o1) {
        //1.空链表 2.一个元素
        if (o1 == null || o1.next == null) {
            return o1;
        }
        ListNode n1 = o1;       //新链表
        ListNode o2 = o1.next;  //旧链表第二个元素
        while (o2 != null) {
            o1.next = o2.next;
            o2.next = n1;
            n1 = o2;
            o2 = o1.next;
        }
        return n1;
    }

    public static ListNode reverseList5(ListNode o1) {
        if (o1 == null || o1.next == null) {
            return o1;
        }
        ListNode n1 = null;
        while (o1 != null) {
            ListNode o2 = o1.next;
            o1.next = n1;
            n1 = o1;
            o1 = o2;
        }

        return n1;
    }

    public static void main(String[] args) {
        ListNode o3 = new ListNode(3, null);
        ListNode o2 = new ListNode(2, o3);
        ListNode o1 = new ListNode(1, o2);
        System.out.println(o1);

//        ListNode n1 = E01LeetCode206.reverseList1(o1);
//        ListNode n1 = E01LeetCode206.reverseList2(o1);
//        ListNode n1 = E01LeetCode206.reverseList3(o1);
//        ListNode n1 = E01LeetCode206.reverseList4(o1);
        ListNode n1 = E01LeetCode206.reverseList5(o1);
        System.out.println(n1);
    }
}
